A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
This invention relates generally to methods for recordering data and more particularly to bit and digit reversal methods.
Bit-reverse and digit-reverse routines are routines in which data is reordered based upon its index value from 0 to N-1, where N is the number of points to be bit/digit-reversed.
Discrete transforms are the main users of methods for bit-reverse and digit-reverse. Discrete transforms take discrete inputs in one domain and convert them to discrete inputs of another. For example, a fast fourier transform (FFT) takes a discrete time domain input and transforms it into the discrete frequency domain output (i.e. x(t) greater than xe2x86x92X(jxcfx89t)). Many discrete transforms such as the FFT, discrete cosine transform (DCT), inverse DCT (IDCT), and discrete sine transform (DST), etc. are executed in-place, i.e., use the same memory locations for both the input and output. This is usually done to reduce both data size and complexity. To take full advantage of in-place methods there remains a need for bit/digit-reversing methods.
For example, if the in-place method uses decimation-in-frequency (DIF) decomposition (see for reference Robert D. Strum and Donald E. Kirk, First Principles of Discrete Systems and Digital Signal Processing, Addison-Wesley Publishing Company, 1989, pp. 512-516, hereinafter referred to as xe2x80x9cStrum and Kirkxe2x80x9d) the input would be normal order but the output would be in bit/digit-reverse order as depicted in FIG. 1. In order to view the resulting output in normal order the results need to be bit-reversed. Also note that if the in-place discrete transform uses a decimation-in-time (DIT) (see for reference Strum and Kirk, pp. 495-512) decomposition, the inputs require bit/digit-reversing while the outputs are in normal order.
There is a direct correlation between the normal order and bit-reversed order which can be shown using the example of an in-place discrete transform as shown in FIG. 1. The in-place discrete transforms"" input is a normal order 8-point array, x[N] and the output is a bit-reversed ordered 8-point array, X[N]. The order of storage of the input array x[N] is in normal order so that the array elements x[0]-x[7] line up with their respective memory locations 0-7 as indicated in FIG. 1. The order of storage of the elements in the output array X[N] is in bit-reversed order when compared to their respective memory locations. This is illustrated better in Tables 1.1 and 1.2, shown hereinabove, where the memory locations and the bit-reversed order output are displayed in hex format and bit format, respectively. It can be seen in Table 1.2 that the bit notation of the memory locations and the bit notation of the bit-reversed ordered output are swapped. This is seen even better, as illustrated by the exemplary tree diagram shown in FIG. 2, when viewing the resulting normal order sorting, shown at 22, and bit-reverse order sorting, shown at 24, of a tree 20.
Normal order sorting, as depicted at 22 in the exemplary tree diagram of FIG. 2, is sorted by looking at the most significant bit, n2 in this example, and if the most significant bit is a zero then it is placed in the upper half of the tree 20. If the most significant bit is a one then it is placed in the lower half of the tree 20. Then the top half and bottom half subtrees are sorted using the same criteria on the second most significant bit, n1 in this example. This process is repeated until the array is completely sorted.
Bit-reversed order sorting, as illustrated at 24 in the exemplary tree diagram of FIG. 2, is sorted by looking at the least significant bit, m0, and if the least significant bit is zero then it is placed in the upper half of the tree 20. If the least significant bit is a one then it is placed in the lower half of the tree 20. Then the top half and bottom half subtrees are sorted using the same criteria on the second least significant bit, m1. This process is repeated until the array is completely sorted. From this one can see that to go from bit-reversed order to normal order or visa-versa one simply needs to xe2x80x9creverse the bitsxe2x80x9d of the desired value to produce the appropriate offset from a base memory location (i.e. for desired value X[n2 n1 n0] of a bit reversed array use offset of [n0 n1 n2] from the beginning of the array.) Since the base memory location is zero in this example, the offset is the memory location.
To perform the bit/digit-reversal of an array of data in-place requires the swapping of the values whose indices are the bit/digit-reversal of one another. When traversing an array during a bit/digit-reversal routine the values are not swapped twice (i.e. if memory location [001] is swapped with [100] then do not swap [100] with [001]) otherwise they are placed back in their original order. One way to avoid this is to set i to the bit-reverse of j and then only swap [i] with [j] if i less than j; this ensures that a double swapping error does not occur.
Digit-reversal is similar to bit-reversal; actually, bit-reversal is the single digit case of digit-reversal. Digit reversal reverses digits instead of bits. For example, a radix-4 FFT produces an output whose results are in 2-digit digit-reverse order. To perform the needed 2-digit digit-reverse ordering, the two least significant bits are swapped with the two most significant bits, then the second pair of least significant bits are swapped with the second pair of most significant bits, and so on. An exemplary tree diagram of 2-digit digit-reverse order sorting is depicted in FIG. 3 for a 16-point 2-digit digit-reversed order output.
It would seem easy to generate a quick routine to perform an in-place bit or digit-reverse routine. All one has to do is swap some bits or digits to produce a bit/digit-reversed order to be used as offsets from a base address and make sure that nothing is double swapped. This method produces satisfactory results for a small number of points, but to perform a bit-reverse on 16K (16xc3x971024) points, for example, which is (214), a total of 14 bits need to be manipulated, thus requiring that 7 bit pairs be swapped. Furthermore, this routine would require a central processing unit (xe2x80x9cCPUxe2x80x9d) cycle count on the order of Nlog2N cycles to complete, which is relatively slow.
Thus, what is needed is an fast, simple method to perform in-place bit and digit reversal.
The present invention is a method of performing bit reversal which comprising the steps of identifying number of points in an array to be bit-reversed and performing bit reversal using a common subtree lookup table accordingly.
In another aspect of the present invention, a method of performing digit reversal is provided which includes the steps of identifying the number of points in an array to be digit-reversed and perform digit reversal using a common subtree lookup table accordingly.
In yet another aspect of the present invention, a method of performing bit reversal on an array of N points is provided which includes the steps of performing sorting tree analysis on the array, identifying a common subtree from the analysis, creating a lookup table from the common subtree, and performing bit reversal on the array using the lookup table generated from the common subtree.
In still another aspect of the present invention, a method of performing digit reversal on an array of N points is provided which includes the steps of performing sorting tree analysis on the array, identifying a common subtree from the analysis, creating a lookup table from the common subtree, and performing digit reversal on the array using the lookup table generated from the common subtree.
These and other features of the invention that will be apparent to those skilled in the art from the following detailed description of the invention, taken together with the accompanying drawings.